package algorithm.middle;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: 当 A 的子数组 A[i], A[i+1], ..., A[j] 满足下列条件时，我们称其为湍流子数组：
 *
 *     若 i <= k < j，当 k 为奇数时， A[k] > A[k+1]，且当 k 为偶数时，A[k] < A[k+1]；
 *     或 若 i <= k < j，当 k 为偶数时，A[k] > A[k+1] ，且当 k 为奇数时， A[k] < A[k+1]。
 *
 * 也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。
 *
 * 返回 A 的最大湍流子数组的长度。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-turbulent-subarray
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @description:
 * @date 2021/2/811:45
 * @since V1.0
 */
public class MaxTurbulenceSize978 {

    public static void main(String[] args) {
     int[] arr = {4,8,12,16};
        int i = new MaxTurbulenceSize978().maxTurbulenceSize(arr);
        System.out.println(i);
    }

    public boolean check(int[] arr,int right){
        if (arr[right]>arr[right-1]&&arr[right-2]>arr[right-1]){
            return true;
        }
        if (arr[right]<arr[right-1]&&arr[right-2]<arr[right-1]){
            return true;
        }
        return false;
    }

    //双指针 滑动窗口
    public int maxTurbulenceSize(int[] arr){
        int left = 0;
        int right = 0;
        int count = 0;
        int max = 0;
        while(right<arr.length){
            if (right-left==0){
                count++;
                right++;
                max = Math.max(max,count);
                continue;
            }else if(right-left==1 && arr[right]!=arr[left]){
                count++;
                right++;
                max = Math.max(max,count);
                continue;
            }else if(right-left==1 && arr[right]==arr[left]){
                left = right;
                count = 0;
                continue;
            }
            if (check(arr,right)){
                right++;
                count++;
                max = Math.max(max,count);
            }else {
                right = right - 1;
                left = right;
                count = 0;
            }
        }
        return max;
    }
    /**
     *状态的定义：
     *
     *     定义 up[i] 表示以位置 i 结尾的，并且 arr[i - 1] < arr[i] 的最长湍流子数组长度。
     *     定义 down[i] 表示以位置 i 结尾的，并且 arr[i - 1] > arr[i] 的最长湍流子数组长度。
     *
     * up[i] 和 down[i] 初始化都是 1，因为每个数字本身都是一个最小的湍流子数组。
     * 状态转移方程：
     *
     *     up[i] = down[i - 1] + 1，当 arr[i - 1] < arr[i]；
     *     down[i] = up[i - 1] + 1，当 arr[i - 1] > arr[i]；
     *
     * 解释：湍流子数组的增长和降低是交替的。
     *
     * 作者：fuxuemingzhu
     * 链接：https://leetcode-cn.com/problems/longest-turbulent-subarray/solution/yi-zhang-dong-tu-xiang-jie-dong-tai-gui-wrwvn/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    //动态规划
    public int maxTurbulenceSize2(int[] arr){
        int[] up = new int[arr.length];
        int[] down = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            up[i] = 1;
            down[i] = 1;
        }
        int max = 1;
        for (int i=1;i<arr.length;i++){
            if (arr[i]<arr[i-1]){
                down[i] = up[i-1]+1;
                max = Math.max(max,down[i]);
            }else if(arr[i]>arr[i-1]){
                up[i] = down[i-1]+1;
                max = Math.max(max,up[i]);
            }
        }
        return max;
    }

    //优化版动态规划
    public int maxTurbulenceSize3(int[] arr){
        int up = 1, down = 1, max = 1;
        for (int i=1;i<arr.length;i++){
            if (arr[i]<arr[i-1]){
                down = up+1;
                up = 1;
                max = Math.max(max,down);
            }else if(arr[i]>arr[i-1]){
                up = down+1;
                down = 1;
                max = Math.max(max,up);
            }else {
                up=1;
                down=1;
            }
        }
        return max;
    }
}
